/*
 * @(#)LevenshteinFunction.java
 *
 * Revision:
 * Author                                         Date           
 * --------------------------------------------   ------------   
 * Ana Emilia Victor Barbosa Coutinho             25/06/2012    
 */
package br.edu.ufcg.splab.techniques.reduction.functions.similarity;

import java.io.File;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import br.edu.ufcg.splab.core.InterfaceEdge;
import br.edu.ufcg.splab.generator.TestCase;


public class LevenshteinFunction implements DistanceFunction {

	/**
	 * Retrieve the similarity (number of repeated elements) in two specified paths.
	 * 
	 * @param path1 first test case.
	 * @param path2 second test case.
	 * @return similarity's value between the two paths. 
	 */
	public double getSimilarity(TestCase path1, TestCase path2){
		return getLevenshteinDistance(path1, path2);
	}
	
	/**
     * Provide a string representation of the similarity function to be written.
     * @return The string representation of the similarity function.
     */
	public String getFunctionName(){
		return "Lev";
	}
	
	/*
	 * This function compares two strings, and determines the minimum number of operations 
	 * necessary to transform one string into another.
	 * 
	 * LEVENSHTEIN, V. I. Binary codes capable of correcting deletions, insertions, and reversals.
	 * Soviet Physics Doklady, [S.l.], v.10, n.8, p.707-710, 1966.
	 */
	private double getLevenshteinDistance(TestCase sequence1, TestCase sequence2) {
		int firstSequence = sequence1.getTestCase().size(); //Nodes sequence
		int secondSequence = sequence2.getTestCase().size();  
		double[][] distanceMatrix = new double[firstSequence+1][secondSequence+1]; //ranges from [0] to [size], thus size +1
      
		//The technique considers the labels in the nodes, since it is used for an Activity Diagram
		// The first columns and rows (i = 0 and j = 0) are for default values. (standard configuration of the algorithm) 
		for (int i = 0; i <= firstSequence; i++) {
			distanceMatrix[i][0] = (double)i; 
		}
		for (int j = 0; j <= secondSequence; j++) {
			distanceMatrix[0][j] = (double)j; 
		}
		
		for (int j = 1; j <= secondSequence; j++) { //columns
			for (int i = 1; i <= firstSequence; i++) { //rows
				InterfaceEdge node1 = sequence1.getTestCase().get(i-1);
				InterfaceEdge node2 = sequence2.getTestCase().get(j-1);
				if(node1.toString().equals(node2.toString())){
					distanceMatrix[i][j] = distanceMatrix[i-1][j-1];
				}else{
					distanceMatrix[i][j] = Math.min(Math.min(distanceMatrix[i-1][j]+1.0, distanceMatrix[i][j-1]+1.0),distanceMatrix[i-1][j-1]+1.0);
				}
			}
		}

		
		if(firstSequence > secondSequence){
			return (double) (1 - (distanceMatrix[firstSequence][secondSequence]/(double)firstSequence));	
		}else {
			return (double) (1 - (distanceMatrix[firstSequence][secondSequence]/(double)secondSequence));
		}		
	}
		
	public static List<File> getFileListTGF(String path){
        File filePath = new File(path);
        List<File> fileList = new ArrayList<File>();
        File[] files = filePath.listFiles();
        List<File> fileandFolderList = Arrays.asList(files);
        for (File file : fileandFolderList) {
        	if(file.getName().substring(file.getName().length() - 3, file.getName().length()).equals("tgf")){
        		fileList.add(file);
        	}
        }
        return fileList;
    }
	
}
